Today’s Agenda

  • Motivation
  • Hausmann’s Curious Question
  • Latschev’s remarkable (but qualitative!) answer
  • Finite reconstruction problem
  • Quantitative Latschev’s theorem
    • abstract manifolds
    • Euclidean submanifolds
  • Extension to \(\mathrm{CAT}(\kappa)\) Spaces
  • Questions

The Vietoris–Rips Complexes

  • a metric space \((X,d_X)\)

    • a scale \(\beta>0\)

    • \(\mathcal{R}_\beta(X)\) is an abstract simplicial complex such that

      • \(X\) is the vertex set
      • each subset \(A\subset X\) of \((k+1)\) points with diameter at most \(\beta\) is a \(k\)-simplex.

Hausmann’s Theorem

Hausmann (1995)

For any closed Riemannian manifold \(M\) and \(0<\beta<\rho(M)\), the Vietoris–Rips complex \(\mathcal{R}_\beta(M)\) is homotopy equivalent to \(M\).

  • vertex set is the entire manifold \(M\)
  • Convexity Radius \(\rho(M)\) is the largest (sup) radius so that geodesic balls are convex.
    • \(\rho(S^1)=\frac{\pi}{2}\)
    • \(\rho(M)>0\) for a compact manifold

Finite Reconstruction Problem

Hausmann’s Curious Question

What about the Vietoris–Rips complex of a dense subset \(X\subset M\)? More generally, for a sample with a small \(d_{GH}(M,X)\).

  • The Rips alternative to Nerve Lemma
  • Manifold reconstruction from a dense subset

Hausdorff and Gromov–Hausdorff Distances

Gromov–Hausdorff Distance:

  • provides the noise model for our reconstruction problem
  • similarity measure between abstract metric spaces \((X,d_X)\) and \((Y,d_Y)\)
  • Definition: \(d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))\)
    • inf over metric spaces \((Z,d_Z)\) and isometries \(f:X\to Z\), \(g:Y\to Z\)

See (Adams et al. 2023) for more details on the relation between the Gromov–Hausdorff and Hausdorff distances.

Latschev’s Remarkable Solution

Latschev’s Theorem (Latschev 2001)

For every closed Riemannian manifold \(M\), there exists a positive number \(\epsilon_0\) such that for any \(0<\beta\leq\epsilon_0\) there exists some \(\delta>0\) such that for every metric space \(X\) with Gromov–Hausdorff distance to \(M\) less than \(\delta\), the Vietoris–Rips complex \(\mathcal R_\beta(X)\) is homotopy equivalent to \(M\).

Key points:

  • The result is qualitative

  • the threshold \(\epsilon_0=\epsilon_0(M)\) depends solely on the geometry of \(M\). But the theorem did not say how!

  • \(\delta=\delta(\beta)\) is a function (probably a fraction) of \(\beta\).

  • Nonetheless, the result answers Hausmann’s question!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction (Majhi 2023b)

Let \((G,d_G)\) be a compact, path-connected metric graph, \((X,d_X)\) a metric space, and \(\beta>0\) a number such that \[3d_{GH}(G,X)<\beta<3\rho(G)/4.\] Then, \(\mathcal R_\beta(X)\simeq G\).

Key points:

  • The result is quantitative

  • \(\epsilon_0=3\rho(G)/4\)

  • \(\delta=\beta/3\)

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction (Majhi 2023a)

Let \((M,d_M)\) be a closed, connected Riemannian manifold. Let \((X,d_X)\) be a compact metric space and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{GH}(M,X)<\beta<\frac{1}{1+2\zeta}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} \] for some \(0<\zeta\leq1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\kappa\) is an upper bound on the sectional curvatures of \(M\)

  • For \(\zeta=\frac{1}{14}\):

    • \(\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}\)

    • \(\delta=\frac{\beta}{14}\)

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2023a)

Let \(M\subset\mathbb R^N\) be a closed, connected submanifold. Let \(X\subset\mathbb R^N\) be a compact subset and \(\beta>0\) a number such that \[ \frac{1}{\zeta}d_{H}(M,X)<\beta<\frac{3(1+2\zeta)(1-14\zeta)}{8(1-2\zeta)^2}\tau(M) \] for some \(0<\zeta<1/14\). Then, \(\mathcal R_\beta(X)\simeq M\).

Key points:

  • \(\tau(M)\) is the reach of \(M\)

  • For \(\zeta=\frac{1}{28}\):

    • \(\epsilon_0=\frac{315}{1352}\tau(M)\)

    • \(\delta=\frac{\beta}{28}\)

Beyond Manifolds

Define CAT spaces

Lastchev’s Theorem for Abstract CAT Spaces

Lastchev’s Theorem for Euclidean CAT Spaces

Discussions

References

Adams, Henry, Florian Frick, Sushovan Majhi, and Nicholas McBride. 2023. “Hausdorff Vs Gromov–Hausdorff Distances.” arXiv Preprint arXiv:2309.16648.
Chazal, Frédéric, Ruqi Huang, and Jian Sun. 2015. “Gromov–Hausdorff Approximation of Filamentary Structures Using Reeb-Type Graphs.” Discrete & Computational Geometry 53 (3): 621–49. https://doi.org/10.1007/s00454-015-9674-1.
Ge, Xiaoyin, Issam Safa, Mikhail Belkin, and Yusu Wang. 2011. “Data Skeletonization via Reeb Graphs.” In Advances in Neural Information Processing Systems, edited by J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger. Vol. 24. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2011/file/3a0772443a0739141292a5429b952fe6-Paper.pdf.
Hausmann, Jean-Claude. 1995. “On the Vietoris-Rips Complexes and a Cohomology Theory for Metric Spaces.” In Prospects in Topology (AM-138), 175–88. Princeton University Press.
Komendarczyk, Rafal, Sushovan Majhi, and Will Tran. 2024. “Topological Stability and Latschev-Type Reconstruction Theorems for \(\boldsymbol{\mathrm{CAT}(κ)}\) Spaces.”
Latschev, J. 2001. “Vietoris-Rips Complexes of Metric Spaces Near a Closed Riemannian Manifold.” Archiv Der Mathematik 77 (6): 522–28. https://doi.org/10.1007/PL00000526.
Majhi, Sushovan. 2023a. “Demystifying Latschev’s Theorem: Manifold Reconstruction from Noisy Data.”
arXiv:2204.14234 [Math.AT]. https://doi.org/10.48550/ARXIV.2305.17288.
———. 2023b. “VietorisRips Complexes of Metric Spaces Near a Metric Graph.” Journal of Applied and Computational Topology, May. https://doi.org/10.1007/s41468-023-00122-z.